package 极客算法训练营.chapter11;

public class 搜索二维矩阵 {
    class Solution1 {
        public boolean searchMatrix(int[][] matrix, int target) {
            int rowSize = matrix.length;
            int colSize = matrix[0].length;
            if (target < matrix[0][0]) {
                return false;
            }
            int row = 0;
            while (row < rowSize && matrix[row][0] <= target) {
                row++;
            }
            for (int i = 0; i < colSize; i++) {
                if (matrix[row - 1][i] == target) return true;
            }
            return false;
        }
        class Solution {
            public boolean searchMatrix(int[][] matrix, int target) {
                int rowSize = matrix.length;
                int colSize = matrix[0].length;
                if (target < matrix[0][0]) {
                    return false;
                }
                int rowL = 0, rowR = rowSize - 1;
                int colL = 0, colR = colSize - 1;
                int rowMid = 0, colMid = 0;
                while (rowL <= rowR) {
                    rowMid = (rowL + rowR) / 2;
                    if (target == matrix[rowMid][0]) {
                        return true;
                    } else if (target < matrix[rowMid][0]) {
                        rowR = rowMid - 1;
                    } else {
                        rowL = rowMid + 1;
                    }
                }
                while (colL <= colR) {
                    colMid = (colL + colR) / 2;
                    if (target == matrix[rowL][colMid]) {
                        return true;
                    } else if (target < matrix[rowL][colMid]) {
                        colMid = colR - 1;
                    } else {
                        colMid = colL + 1;
                    }
                }
                return false;
            }
        }
    }
}
